{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color='green'> Benchmarking - Graph Algorithms <font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color='green'> 1. Description<font>\n",
    "\n",
    "We are using below datasets for Graph Algorithms.\n",
    "\n",
    " **preferentialAttachment:** \n",
    " \n",
    "  Dataset can be downloaded from https://sparse.tamu.edu/MM/DIMACS10/preferentialAttachment.tar.gz\n",
    "  \n",
    "  This graph has been generated following a preferential attachment process. Starting with a clique of five vertices, the vertices are successively added to the graph. Each new vertex chooses exactly five neighbors among the existing vertices, such that the probability of choosing a particular vertex is proportional to its degree.\n",
    " \n",
    " **caidaRouterLevel:**\n",
    " \n",
    "  Dataset can be downloaded from https://sparse.tamu.edu/MM/DIMACS10/caidaRouterLevel.tar.gz\n",
    "    \n",
    "**coAuthorsDBLP:**\n",
    " \n",
    "  Dataset can be downloaded from https://sparse.tamu.edu/MM/DIMACS10/coAuthorsDBLP.tar.gz\n",
    " \n",
    "  This is a Co-Authorship Network where two authors are connected if they publish at least one paper together.\n",
    "\n",
    "**dblp-2010:**\n",
    "  \n",
    "  Dataset can be downloaded from https://sparse.tamu.edu/MM/LAW/dblp-2010.tar.gz\n",
    "  \n",
    "  DBLP is a bibliography service from which an undirected scientific collaboration network can be extracted: each vertex  represents a scientist and two vertices are connected if they have worked together on an article. \n",
    "\n",
    "**citationCitesee:**\n",
    "\n",
    "  Dataset can be downloaded from https://sparse.tamu.edu/MM/DIMACS10/citationCiteseer.tar.gz\n",
    "\n",
    "  Citation network dataset published by DIMACS10. In this, the nodes represents a paper and edges represents a citation\n",
    "    \n",
    "**coPapersDBLP:**\n",
    "\n",
    "  Dataset can be downloaded from https://sparse.tamu.edu/MM/DIMACS10/coPapersDBLP.tar.gz\n",
    "\n",
    "  Citation network dataset published by DIMACS10. Here, the nodes represent scientists, edges represent collaborations (co-authoring a paper)\n",
    "    \n",
    "**coPapersCiteseer:**\n",
    " \n",
    "  Dataset can be downloaded from https://sparse.tamu.edu/MM/DIMACS10/coPapersCiteseer.tar.gz\n",
    "\n",
    "  Visualize coPapersCiteseer's link structure and discover valuable insights using our interactive graph visualization platform. Compare with hundreds of other networks across many different collections and types.\n",
    "\n",
    "**as-Skitter:**\n",
    "    \n",
    "  Dataset can be downloaded from https://sparse.tamu.edu/MM/SNAP/as-Skitter.tar.gz\n",
    "    \n",
    "  This is Internet Topology datasets. Skitter is a tool for actively probing the Internet in order to analyze topology and performance. Skitter was also used in reference to the Macroscopic Topology Measurements Project and the Skitter infrastructure, which has since been replaced with the Archipelago (Ark) infrastructure."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color='green'> 2. Data Preprocessing<font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "import sys\n",
    "import time\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import networkx as nx\n",
    "import frovedis.graph as fnx\n",
    "from collections import OrderedDict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Please uncomment the below lines to download and unzip the dataset. We have removed the comments including the very first line with graph details\n",
    "\n",
    "#dataset_links = {\n",
    "#    'preferentialAttachment' : 'https://sparse.tamu.edu/MM/DIMACS10/preferentialAttachment.tar.gz',\n",
    "#    'caidaRouterLevel'       : 'https://sparse.tamu.edu/MM/DIMACS10/caidaRouterLevel.tar.gz',\n",
    "#    'coAuthorsDBLP'          : 'https://sparse.tamu.edu/MM/DIMACS10/coAuthorsDBLP.tar.gz',\n",
    "#    'dblp-2010'              : 'https://sparse.tamu.edu/MM/LAW/dblp-2010.tar.gz',\n",
    "#    'citationCiteseer'       : 'https://sparse.tamu.edu/MM/DIMACS10/citationCiteseer.tar.gz',\n",
    "#    'coPapersDBLP'           : 'https://sparse.tamu.edu/MM/DIMACS10/coPapersDBLP.tar.gz',\n",
    "#    'coPapersCiteseer'       : 'https://sparse.tamu.edu/MM/DIMACS10/coPapersCiteseer.tar.gz',\n",
    "#    'as-Skitter'             : 'https://sparse.tamu.edu/MM/SNAP/as-Skitter.tar.gz'\n",
    "#}\n",
    "#for name, link in dataset_links.items():\n",
    "#    !wget -N  {link}\n",
    "#    !tar -xf {name + '.tar.gz'}\n",
    "#    !mv {name}/{name+'.mtx'} datasets\n",
    "\n",
    "# Load dataset\n",
    "input_graph_files = {\n",
    "    'preferentialAttachment' : './datasets/preferentialAttachment.mtx',\n",
    "    'caidaRouterLevel'       : './datasets/caidaRouterLevel.mtx',\n",
    "    'coAuthorsDBLP'          : './datasets/coAuthorsDBLP.mtx',\n",
    "    'dblp'                   : './datasets/dblp-2010.mtx',\n",
    "    'citationCiteseer'       : './datasets/citationCiteseer.mtx',\n",
    "    'coPapersDBLP'           : './datasets/coPapersDBLP.mtx',\n",
    "    'coPapersCiteseer'       : './datasets/coPapersCiteseer.mtx',\n",
    "    'as-Skitter'             : './datasets/as-Skitter.mtx'\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from frovedis.exrpc.server import FrovedisServer\n",
    "FrovedisServer.initialize(\"mpirun -np 8 \" + os.environ[\"FROVEDIS_SERVER\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color='green'> 3. Algorithm Evaluation<font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3.1 Graph Loading Demo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# -------- Graph loading demo --------\n",
    "frov_data_loading_time = []\n",
    "nx_data_loading_time = []\n",
    "frov_graph = []\n",
    "frov_graph_dir = []\n",
    "nx_graph = []\n",
    "nx_graph_dir = []\n",
    "nnodes = []\n",
    "nedges = []\n",
    "\n",
    "for dataset, path in input_graph_files.items():\n",
    "    dl_start_time = time.time()\n",
    "    fgraph = fnx.read_edgelist(path, nodetype=np.int32, delimiter=' ')\n",
    "    # for pagerank etc. we will use directed graph for better ranking\n",
    "    fgraph_dir = fnx.read_edgelist(path, nodetype=np.int32, delimiter=' ', \\\n",
    "                                   create_using=nx.DiGraph())\n",
    "    frov_data_loading_time.append(round(time.time() - dl_start_time, 4))\n",
    "    frov_graph.append(fgraph)\n",
    "    frov_graph_dir.append(fgraph_dir)\n",
    "    \n",
    "    dl_start_time = time.time()\n",
    "    ngraph = nx.read_edgelist(path, nodetype=np.int32, delimiter=' ')\n",
    "    # for pagerank etc. we will use directed graph for better ranking\n",
    "    ngraph_dir = nx.read_edgelist(path, nodetype=np.int32, delimiter=' ', \\\n",
    "                                  create_using=nx.DiGraph())\n",
    "    nx_data_loading_time.append(round(time.time() - dl_start_time, 4))\n",
    "    nx_graph.append(ngraph)\n",
    "    nx_graph_dir.append(ngraph_dir)\n",
    "\n",
    "    nnodes.append(ngraph.number_of_nodes())\n",
    "    nedges.append(ngraph.number_of_edges())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>dataset</th>\n",
       "      <th>num_nodes</th>\n",
       "      <th>num_edges</th>\n",
       "      <th>frov_loading_time</th>\n",
       "      <th>nx_loading_time</th>\n",
       "      <th>frov_speed_up</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>preferentialAttachment</td>\n",
       "      <td>100000</td>\n",
       "      <td>499985</td>\n",
       "      <td>0.4130</td>\n",
       "      <td>5.9338</td>\n",
       "      <td>14.367554</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>caidaRouterLevel</td>\n",
       "      <td>192244</td>\n",
       "      <td>609066</td>\n",
       "      <td>0.4993</td>\n",
       "      <td>7.5316</td>\n",
       "      <td>15.084318</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>coAuthorsDBLP</td>\n",
       "      <td>299067</td>\n",
       "      <td>977676</td>\n",
       "      <td>0.7140</td>\n",
       "      <td>12.3610</td>\n",
       "      <td>17.312325</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>dblp</td>\n",
       "      <td>300647</td>\n",
       "      <td>807700</td>\n",
       "      <td>0.7008</td>\n",
       "      <td>10.8511</td>\n",
       "      <td>15.483876</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>citationCiteseer</td>\n",
       "      <td>268495</td>\n",
       "      <td>1156647</td>\n",
       "      <td>0.6922</td>\n",
       "      <td>13.6544</td>\n",
       "      <td>19.726091</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>coPapersDBLP</td>\n",
       "      <td>540486</td>\n",
       "      <td>15245729</td>\n",
       "      <td>10.9483</td>\n",
       "      <td>142.8855</td>\n",
       "      <td>13.050930</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>coPapersCiteseer</td>\n",
       "      <td>434102</td>\n",
       "      <td>16036720</td>\n",
       "      <td>12.0299</td>\n",
       "      <td>152.6621</td>\n",
       "      <td>12.690222</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>as-Skitter</td>\n",
       "      <td>1696415</td>\n",
       "      <td>11095298</td>\n",
       "      <td>13.0069</td>\n",
       "      <td>152.0384</td>\n",
       "      <td>11.689057</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                  dataset  num_nodes  num_edges  frov_loading_time  \\\n",
       "0  preferentialAttachment     100000     499985             0.4130   \n",
       "1        caidaRouterLevel     192244     609066             0.4993   \n",
       "2           coAuthorsDBLP     299067     977676             0.7140   \n",
       "3                    dblp     300647     807700             0.7008   \n",
       "4        citationCiteseer     268495    1156647             0.6922   \n",
       "5            coPapersDBLP     540486   15245729            10.9483   \n",
       "6        coPapersCiteseer     434102   16036720            12.0299   \n",
       "7              as-Skitter    1696415   11095298            13.0069   \n",
       "\n",
       "   nx_loading_time  frov_speed_up  \n",
       "0           5.9338      14.367554  \n",
       "1           7.5316      15.084318  \n",
       "2          12.3610      17.312325  \n",
       "3          10.8511      15.483876  \n",
       "4          13.6544      19.726091  \n",
       "5         142.8855      13.050930  \n",
       "6         152.6621      12.690222  \n",
       "7         152.0384      11.689057  "
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data_details = pd.DataFrame(OrderedDict({ \"dataset\": list(input_graph_files.keys()),\n",
    "                                \"num_nodes\": nnodes,\n",
    "                                \"num_edges\": nedges,\n",
    "                                \"frov_loading_time\": frov_data_loading_time,\n",
    "                                \"nx_loading_time\": nx_data_loading_time\n",
    "                             }))\n",
    "data_details[\"frov_speed_up\"] = data_details[\"nx_loading_time\"] / data_details[\"frov_loading_time\"]\n",
    "data_details"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3.2 Single Source Shortest Path (SSSP)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "src = 5\n",
    "frov_sssp_time = []\n",
    "nx_sssp_time = []\n",
    "dist_matched = []\n",
    "\n",
    "for i in range(len(frov_graph)):\n",
    "    start_time = time.time()\n",
    "    fpath, fdist = fnx.single_source_shortest_path(frov_graph[i], \\\n",
    "                   src, return_distance=True)\n",
    "    frov_sssp_time.append(round(time.time() - start_time, 4))\n",
    "\n",
    "    #print(\"frovedis: distance for {} dataset\".format(dataset))\n",
    "    #print(fdist)\n",
    "\n",
    "    start_time = time.time()\n",
    "    npath = nx.single_source_shortest_path(nx_graph[i], src)\n",
    "    nx_sssp_time.append(round(time.time() - start_time, 4))\n",
    "\n",
    "    ndist = {k: float(len(v)-1) for k, v in npath.items()}\n",
    "    #print(\"networkx: distance for {} dataset\".format(dataset))\n",
    "    #print(ndist)\n",
    "\n",
    "    dist_matched.append(\"Yes\" if fdist == ndist else \"No\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>dataset</th>\n",
       "      <th>frov_sssp_time</th>\n",
       "      <th>nx_sssp_time</th>\n",
       "      <th>result_matched</th>\n",
       "      <th>frov_speed_up</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>preferentialAttachment</td>\n",
       "      <td>0.0423</td>\n",
       "      <td>0.3782</td>\n",
       "      <td>Yes</td>\n",
       "      <td>8.940898</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>caidaRouterLevel</td>\n",
       "      <td>0.0887</td>\n",
       "      <td>0.6021</td>\n",
       "      <td>Yes</td>\n",
       "      <td>6.788050</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>coAuthorsDBLP</td>\n",
       "      <td>0.1059</td>\n",
       "      <td>24.6352</td>\n",
       "      <td>Yes</td>\n",
       "      <td>232.627007</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>dblp</td>\n",
       "      <td>0.0842</td>\n",
       "      <td>0.7880</td>\n",
       "      <td>Yes</td>\n",
       "      <td>9.358670</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>citationCiteseer</td>\n",
       "      <td>0.0948</td>\n",
       "      <td>1.1186</td>\n",
       "      <td>Yes</td>\n",
       "      <td>11.799578</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>coPapersDBLP</td>\n",
       "      <td>0.2040</td>\n",
       "      <td>4.3748</td>\n",
       "      <td>Yes</td>\n",
       "      <td>21.445098</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>coPapersCiteseer</td>\n",
       "      <td>0.1820</td>\n",
       "      <td>4.3377</td>\n",
       "      <td>Yes</td>\n",
       "      <td>23.833516</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>as-Skitter</td>\n",
       "      <td>0.7244</td>\n",
       "      <td>33.6921</td>\n",
       "      <td>Yes</td>\n",
       "      <td>46.510353</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                  dataset  frov_sssp_time  nx_sssp_time result_matched  \\\n",
       "0  preferentialAttachment          0.0423        0.3782            Yes   \n",
       "1        caidaRouterLevel          0.0887        0.6021            Yes   \n",
       "2           coAuthorsDBLP          0.1059       24.6352            Yes   \n",
       "3                    dblp          0.0842        0.7880            Yes   \n",
       "4        citationCiteseer          0.0948        1.1186            Yes   \n",
       "5            coPapersDBLP          0.2040        4.3748            Yes   \n",
       "6        coPapersCiteseer          0.1820        4.3377            Yes   \n",
       "7              as-Skitter          0.7244       33.6921            Yes   \n",
       "\n",
       "   frov_speed_up  \n",
       "0       8.940898  \n",
       "1       6.788050  \n",
       "2     232.627007  \n",
       "3       9.358670  \n",
       "4      11.799578  \n",
       "5      21.445098  \n",
       "6      23.833516  \n",
       "7      46.510353  "
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sssp_df = pd.DataFrame(OrderedDict ({ \"dataset\": list(input_graph_files.keys()),\n",
    "                                      \"frov_sssp_time\": frov_sssp_time,\n",
    "                                      \"nx_sssp_time\": nx_sssp_time,\n",
    "                                      \"result_matched\": dist_matched\n",
    "                                   }))\n",
    "sssp_df[\"frov_speed_up\"] = sssp_df[\"nx_sssp_time\"] / sssp_df[\"frov_sssp_time\"]\n",
    "sssp_df"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3.3 PageRank"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "frov_pr_time = []\n",
    "nx_pr_time = []\n",
    "order_matched = []\n",
    "\n",
    "#pagerank uses directed graph for generating better numerical ranks\n",
    "for i in range(len(frov_graph_dir)):\n",
    "    start_time = time.time()\n",
    "    frov_ranks = fnx.pagerank(frov_graph_dir[i])\n",
    "    frov_pr_time.append(round(time.time() - start_time, 4))\n",
    "    df1 = pd.DataFrame({ \"node\": list(frov_ranks.keys()),\n",
    "                         \"rank\": list(frov_ranks.values())\n",
    "                       }) \\\n",
    "            .sort_values(by = [\"rank\", \"node\"]) \\\n",
    "            .head(10)\n",
    "    #print(df1)\n",
    "\n",
    "    start_time = time.time()\n",
    "    nx_ranks = nx.pagerank(nx_graph_dir[i])\n",
    "    nx_pr_time.append(round(time.time() - start_time, 4))\n",
    "    df2 = pd.DataFrame({ \"node\": list(nx_ranks.keys()),\n",
    "                         \"rank\": list(nx_ranks.values())\n",
    "                       }) \\\n",
    "            .sort_values(by = [\"rank\", \"node\"]) \\\n",
    "            .head(10)\n",
    "    #print(df2)\n",
    "    order_matched.append(\"Yes\" if list(df1.node.values) == list(df2.node.values) else \"No\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>dataset</th>\n",
       "      <th>frov_pr_time</th>\n",
       "      <th>nx_pr_time</th>\n",
       "      <th>ranking_order_matched</th>\n",
       "      <th>frov_speed_up</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>preferentialAttachment</td>\n",
       "      <td>0.0226</td>\n",
       "      <td>10.7416</td>\n",
       "      <td>Yes</td>\n",
       "      <td>475.292035</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>caidaRouterLevel</td>\n",
       "      <td>0.0397</td>\n",
       "      <td>10.8338</td>\n",
       "      <td>Yes</td>\n",
       "      <td>272.891688</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>coAuthorsDBLP</td>\n",
       "      <td>0.0596</td>\n",
       "      <td>14.3700</td>\n",
       "      <td>Yes</td>\n",
       "      <td>241.107383</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>dblp</td>\n",
       "      <td>0.0838</td>\n",
       "      <td>11.0422</td>\n",
       "      <td>Yes</td>\n",
       "      <td>131.768496</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>citationCiteseer</td>\n",
       "      <td>0.0494</td>\n",
       "      <td>16.3914</td>\n",
       "      <td>Yes</td>\n",
       "      <td>331.809717</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>coPapersDBLP</td>\n",
       "      <td>0.0978</td>\n",
       "      <td>135.4959</td>\n",
       "      <td>Yes</td>\n",
       "      <td>1385.438650</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>coPapersCiteseer</td>\n",
       "      <td>0.1104</td>\n",
       "      <td>112.3445</td>\n",
       "      <td>Yes</td>\n",
       "      <td>1017.613225</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>as-Skitter</td>\n",
       "      <td>0.2974</td>\n",
       "      <td>112.0632</td>\n",
       "      <td>Yes</td>\n",
       "      <td>376.809684</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                  dataset  frov_pr_time  nx_pr_time ranking_order_matched  \\\n",
       "0  preferentialAttachment        0.0226     10.7416                   Yes   \n",
       "1        caidaRouterLevel        0.0397     10.8338                   Yes   \n",
       "2           coAuthorsDBLP        0.0596     14.3700                   Yes   \n",
       "3                    dblp        0.0838     11.0422                   Yes   \n",
       "4        citationCiteseer        0.0494     16.3914                   Yes   \n",
       "5            coPapersDBLP        0.0978    135.4959                   Yes   \n",
       "6        coPapersCiteseer        0.1104    112.3445                   Yes   \n",
       "7              as-Skitter        0.2974    112.0632                   Yes   \n",
       "\n",
       "   frov_speed_up  \n",
       "0     475.292035  \n",
       "1     272.891688  \n",
       "2     241.107383  \n",
       "3     131.768496  \n",
       "4     331.809717  \n",
       "5    1385.438650  \n",
       "6    1017.613225  \n",
       "7     376.809684  "
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pagerank_df = pd.DataFrame(OrderedDict ({ \"dataset\": list(input_graph_files.keys()),\n",
    "                             \"frov_pr_time\": frov_pr_time,\n",
    "                             \"nx_pr_time\": nx_pr_time,\n",
    "                             \"ranking_order_matched\": order_matched\n",
    "                          }))\n",
    "pagerank_df[\"frov_speed_up\"] = pagerank_df[\"nx_pr_time\"] / pagerank_df[\"frov_pr_time\"]\n",
    "pagerank_df"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3.4 Breadth First Search (BFS)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "source = 1\n",
    "distance = 4 \n",
    "frov_bfs_time = []\n",
    "nx_bfs_time = []\n",
    "result_matched = []\n",
    "\n",
    "for i in range(len(frov_graph)):\n",
    "    start_time = time.time()\n",
    "    frov_res = fnx.descendants_at_distance(frov_graph[i], source, distance)\n",
    "    frov_bfs_time.append(round(time.time() - start_time, 4))\n",
    "    #print(list(frov_res)[:5])\n",
    "\n",
    "    start_time = time.time()\n",
    "    nx_res = nx.descendants_at_distance(nx_graph[i], source, distance)\n",
    "    nx_bfs_time.append(round(time.time() - start_time, 4))\n",
    "    #print(list(nx_res)[:5])\n",
    "\n",
    "    result_matched.append(\"Yes\" if len(frov_res - nx_res) == 0 else \"No\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>dataset</th>\n",
       "      <th>frov_bfs_time</th>\n",
       "      <th>nx_bfs_time</th>\n",
       "      <th>result_matched</th>\n",
       "      <th>frov_speed_up</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>preferentialAttachment</td>\n",
       "      <td>0.0169</td>\n",
       "      <td>0.3470</td>\n",
       "      <td>Yes</td>\n",
       "      <td>20.532544</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>caidaRouterLevel</td>\n",
       "      <td>0.0176</td>\n",
       "      <td>0.0864</td>\n",
       "      <td>Yes</td>\n",
       "      <td>4.909091</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>coAuthorsDBLP</td>\n",
       "      <td>0.0103</td>\n",
       "      <td>0.0025</td>\n",
       "      <td>Yes</td>\n",
       "      <td>0.242718</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>dblp</td>\n",
       "      <td>0.0091</td>\n",
       "      <td>0.0007</td>\n",
       "      <td>Yes</td>\n",
       "      <td>0.076923</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>citationCiteseer</td>\n",
       "      <td>0.0106</td>\n",
       "      <td>0.0087</td>\n",
       "      <td>Yes</td>\n",
       "      <td>0.820755</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>coPapersDBLP</td>\n",
       "      <td>0.0185</td>\n",
       "      <td>0.0467</td>\n",
       "      <td>Yes</td>\n",
       "      <td>2.524324</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>coPapersCiteseer</td>\n",
       "      <td>0.0144</td>\n",
       "      <td>0.0205</td>\n",
       "      <td>Yes</td>\n",
       "      <td>1.423611</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>as-Skitter</td>\n",
       "      <td>0.1782</td>\n",
       "      <td>3.8218</td>\n",
       "      <td>Yes</td>\n",
       "      <td>21.446689</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                  dataset  frov_bfs_time  nx_bfs_time result_matched  \\\n",
       "0  preferentialAttachment         0.0169       0.3470            Yes   \n",
       "1        caidaRouterLevel         0.0176       0.0864            Yes   \n",
       "2           coAuthorsDBLP         0.0103       0.0025            Yes   \n",
       "3                    dblp         0.0091       0.0007            Yes   \n",
       "4        citationCiteseer         0.0106       0.0087            Yes   \n",
       "5            coPapersDBLP         0.0185       0.0467            Yes   \n",
       "6        coPapersCiteseer         0.0144       0.0205            Yes   \n",
       "7              as-Skitter         0.1782       3.8218            Yes   \n",
       "\n",
       "   frov_speed_up  \n",
       "0      20.532544  \n",
       "1       4.909091  \n",
       "2       0.242718  \n",
       "3       0.076923  \n",
       "4       0.820755  \n",
       "5       2.524324  \n",
       "6       1.423611  \n",
       "7      21.446689  "
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bfs_df = pd.DataFrame(OrderedDict ({ \"dataset\": list(input_graph_files.keys()),\n",
    "                        \"frov_bfs_time\": frov_bfs_time,\n",
    "                        \"nx_bfs_time\": nx_bfs_time,\n",
    "                        \"result_matched\": result_matched\n",
    "                     }))\n",
    "bfs_df[\"frov_speed_up\"] = bfs_df[\"nx_bfs_time\"] / bfs_df[\"frov_bfs_time\"]\n",
    "bfs_df"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3.5 Connected Components (CC)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# -------- connected components demo --------\n",
    "frov_cc_time = []\n",
    "nx_cc_time = []\n",
    "frov_ncomponents = []\n",
    "nx_ncomponents = []\n",
    "result_matched = []\n",
    "\n",
    "for i in range(len(frov_graph)):\n",
    "    start_time = time.time()\n",
    "    tmp = fnx.connected_components(frov_graph[i])\n",
    "    set_cc_frov = set()\n",
    "    for elem in tmp:\n",
    "        set_cc_frov.add(frozenset(elem))\n",
    "    frov_cc_time.append(round(time.time() - start_time, 4))\n",
    "    frov_ncomponents.append(len(set_cc_frov))\n",
    "\n",
    "    start_time = time.time()\n",
    "    tmp = nx.connected_components(nx_graph[i])\n",
    "    set_cc_nx = set()\n",
    "    for elem in tmp:\n",
    "        set_cc_nx.add(frozenset(elem))\n",
    "    nx_cc_time.append(round(time.time() - start_time, 4))\n",
    "    nx_ncomponents.append(len(set_cc_nx))\n",
    "\n",
    "    result_matched.append(\"Yes\" if set_cc_frov == set_cc_nx else \"No\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>dataset</th>\n",
       "      <th>frov_cc_time</th>\n",
       "      <th>nx_cc_time</th>\n",
       "      <th>frov_ncomponents</th>\n",
       "      <th>nx_ncomponents</th>\n",
       "      <th>result_matched</th>\n",
       "      <th>frov_speed_up</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>preferentialAttachment</td>\n",
       "      <td>0.0892</td>\n",
       "      <td>0.2807</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>Yes</td>\n",
       "      <td>3.146861</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>caidaRouterLevel</td>\n",
       "      <td>0.2706</td>\n",
       "      <td>0.5020</td>\n",
       "      <td>308</td>\n",
       "      <td>308</td>\n",
       "      <td>Yes</td>\n",
       "      <td>1.855137</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>coAuthorsDBLP</td>\n",
       "      <td>0.2603</td>\n",
       "      <td>0.7829</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>Yes</td>\n",
       "      <td>3.007683</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>dblp</td>\n",
       "      <td>3.1094</td>\n",
       "      <td>0.6905</td>\n",
       "      <td>22954</td>\n",
       "      <td>22954</td>\n",
       "      <td>Yes</td>\n",
       "      <td>0.222069</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>citationCiteseer</td>\n",
       "      <td>0.2537</td>\n",
       "      <td>0.9657</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>Yes</td>\n",
       "      <td>3.806464</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>coPapersDBLP</td>\n",
       "      <td>0.4972</td>\n",
       "      <td>3.4103</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>Yes</td>\n",
       "      <td>6.859010</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>coPapersCiteseer</td>\n",
       "      <td>0.4121</td>\n",
       "      <td>3.9138</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>Yes</td>\n",
       "      <td>9.497209</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>as-Skitter</td>\n",
       "      <td>1.6324</td>\n",
       "      <td>6.4308</td>\n",
       "      <td>756</td>\n",
       "      <td>756</td>\n",
       "      <td>Yes</td>\n",
       "      <td>3.939476</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                  dataset  frov_cc_time  nx_cc_time  frov_ncomponents  \\\n",
       "0  preferentialAttachment        0.0892      0.2807                 1   \n",
       "1        caidaRouterLevel        0.2706      0.5020               308   \n",
       "2           coAuthorsDBLP        0.2603      0.7829                 1   \n",
       "3                    dblp        3.1094      0.6905             22954   \n",
       "4        citationCiteseer        0.2537      0.9657                 1   \n",
       "5            coPapersDBLP        0.4972      3.4103                 1   \n",
       "6        coPapersCiteseer        0.4121      3.9138                 1   \n",
       "7              as-Skitter        1.6324      6.4308               756   \n",
       "\n",
       "   nx_ncomponents result_matched  frov_speed_up  \n",
       "0               1            Yes       3.146861  \n",
       "1             308            Yes       1.855137  \n",
       "2               1            Yes       3.007683  \n",
       "3           22954            Yes       0.222069  \n",
       "4               1            Yes       3.806464  \n",
       "5               1            Yes       6.859010  \n",
       "6               1            Yes       9.497209  \n",
       "7             756            Yes       3.939476  "
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cc_df = pd.DataFrame(OrderedDict ({ \"dataset\": list(input_graph_files.keys()),\n",
    "                        \"frov_cc_time\": frov_cc_time,\n",
    "                        \"nx_cc_time\": nx_cc_time,\n",
    "                        \"frov_ncomponents\": frov_ncomponents,\n",
    "                        \"nx_ncomponents\": nx_ncomponents,\n",
    "                        \"result_matched\": result_matched\n",
    "                     }))\n",
    "cc_df[\"frov_speed_up\"] = cc_df[\"nx_cc_time\"] / cc_df[\"frov_cc_time\"]\n",
    "cc_df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "FrovedisServer.shut_down()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
